package com.example.algorithm.test;

import org.junit.Test;

/**
 * 求 x 的平方根的整数部分
 * @auther lijiewei
 * @date 2024-03-14 19:34
 */
public class SquareRoot {

    /** 二分查找. */
    private int binarySearch (int x) {
        int index = -1;
        int left = 0;
        int right = x;
        while (left <= right) {
            int middle = left + (right-left)/2;
            if (middle * middle <= x) {
                index = middle;
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return index;
    }

    /** 牛顿迭代. */
    private int iteration(int x) {
        if (x <= 0) {
            return -1;
        }
        return (int)sqrt(x, x);
    }

    public double sqrt(double i, int x) {
        double res = (i + x/i)/2;
        if (res == i) {
            return res;
        } else {
            return sqrt(res, x);
        }
    }

    @Test
    public void iterationTest() throws Exception{
        System.out.println(iteration(25));
    }
    @Test
    public void binarySearchTest() throws Exception{
        System.out.println(binarySearch(25));

    }


}
